Chang “Scalable Packet Classification for Enabling Internet Differentiated Services

Abstract—Nowadays, IP networks are rapidly evolving toward a QoS-enabled infrastructure. The need for packet classification is increasing in accordance with emerging differentiated services. While the new differentiated services could significantly increase the number of rules, it has been demonstrated that performing packet classification on a potentially large number of rules is diffi-cult and has poor worst-case performance. In this work, we present an enhanced tuple pruning search algorithm called “Tuple Pruning Plus ” (TPP) for packet classification, which outperforms the ex-isting schemes on the scalability. Our main idea is to simplify the lookup procedure and to avoid unnecessary tuple probing by main-taining the least-cost property of rule through precomputation and the proposed Information Marker. With extra rules added for In-formation Marker, only one tuple access is required in each packet classification. In our experiments, 70 MB DRAM is used to achieve 50 million packets per second (MPPS) for a 1 M-rule set, showing a performance improvement by a factor of 50. We also present a heuristic to further reduce the required storage to about 20 MB. These results demonstrate the effectiveness of the TPP scheme to achieve high speed packet classification. Index Terms—Best matching prefix, multicast, multidimensional range lookup, packet classification. I